算术基本定理基础

算术基本定理基础

算术基本定理

​ 对于任意的实数 xx 有:(部分虚数不满足,例如 5\sqrt{-5}

x=p1α1 p2α2pkαkx=p_1^{\alpha_1}~p_2^{\alpha_2}\cdots p_k^{\alpha_k}

​ 其中对于任意的 pip_i 都是质数,且 pi,αiNp_i,\alpha_i \in \mathbb{N}

阅读全文 »

KMP 匹配算法

KMP 匹配算法

RE:从零开始的字符串学习

暴力做法

​ 首先将两个字符串首位对齐,逐位匹配,完成匹配后将模式串位置后移一位。

​ 时间复杂度为:O(nm)O(nm),其中 n,mn,m 分别表示主串和模式串的长度。

阅读全文 »

鸽巢原理及应用

鸽巢原理及应用

就简单的概述一下了

简单形式

​ 现有 n+1n+1 个物品,要将他们放入 nn 个盒子里,那么必定有 11 个盒子内至少有 22 个物品。

​ 显然,我们考虑每个盒子里都只能放置 11 个物品,那么会有 11 个物品剩余,所以易证。

阅读全文 »

求导基础及常用函数的导数

求导基础及常用函数的导数

一些微积分的基础知识。

关于求导

​ 我们对于一个函数所求的导函数实为:基于其图像中的每一点求其斜率的函数表达式。

f(x)f`(x) 表示函数 f(x)f(x) 的导函数,那么就有:

limh0f(x+h)f(x)h\lim_{h\rightarrow0}\frac{f(x+h)-f(x)}{h}

阅读全文 »

整数分块

整数分块

现在来补一下小知识

例子

i=1nni\sum_{i=1}^{n}\frac{n}{i}

​ 求上式。

阅读全文 »